import java.util.LinkedList
import java.util.Queue

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null

    companion object {
        fun createTreeNode(nodeVals: List<Int?>): TreeNode {
            val n = nodeVals.size
            val head: TreeNode
            var queue1: Queue<TreeNode> = LinkedList()
            queue1.add(TreeNode(nodeVals.first()!!).apply {
                head = this
            })
            var queue2: Queue<TreeNode> = LinkedList()
            var index = 1
            while (index < n) {
                if (queue1.isEmpty() && queue2.isEmpty()) {
                    break
                }
                if (queue1.isEmpty()) {
                    val temp = queue1
                    queue1 = queue2
                    queue2 = temp
                }
                val node = queue1.poll()
                nodeVals[index]?.let {
                    node.left = TreeNode(it)
                    queue2.offer(node.left)
                }
                if (index + 1 < n) {
                    index++
                    nodeVals[index]?.let {
                        node.right = TreeNode(it)
                        queue2.offer(node.right)
                    }
                }
                index++
            }
            return head
        }

    }
}